package BinaryTree;

/**
 * 求一个二叉树最远的两个点的距离
 *
 * @author Liaorun
 */
public class MaxDistanceInTree {

    public static void main(String[] args) {
        Node head1 = new Node(1);
        head1.left = new Node(2);
        head1.right = new Node(3);

        head1.left.left = new Node(4);
        head1.left.right = new Node(5);

        head1.left.left.left = new Node(6);
        head1.left.right.right = new Node(7);
        head1.left.right.right.right = new Node(8);

        System.out.println(maxDistance(head1));
    }

    public static class Node {
        public int value;
        public Node left;
        public Node right;


        public Node(int value) {
            this.value = value;
        }
    }

    public static int maxDistance(Node head) {
        return process(head).maxDistance;
    }

    private static Info process(Node x) {
        // base case
        if (x == null) {
            return new Info(0, 0);
        }
        Info left = process(x.left);
        Info right = process(x.right);

        int p1 = left.maxDistance;
        int p2 = right.maxDistance;
        // 左子树高度 + 右子树高度 + 1 == 一笔画，经过当前节点的路径的情况下，最长的距离（最远两个节点的距离）
        int p3 = left.height + 1 + right.height;

        // 当前树的一笔画最远距离为，当前节点和两个子节点的一笔画距离比较，最大的哪一个
        int maxDistance = Math.max(p3, Math.max(p1, p2));

        // 当前节点高度 = 最好的子节点的高度 + 1
        int height = Math.max(left.height, right.height) + 1;
        return new Info(maxDistance, height);
    }

    public static class Info {
        public int maxDistance;
        public int height;


        public Info(int maxDistance, int height) {
            this.maxDistance = maxDistance;
            this.height = height;
        }
    }
}
